#include<iostream>
using namespace std;

void InsertSort(int* a,int n)
{
    int i=0;
    for(i=0;i<n-1;i++)
    {
        int end=i;
        int tmp=a[end+1];
        while(end>=0)
        {
            if(a[end]>tmp)
            {
                a[end+1]=a[end];
                end--;
            }
            else{
                break;
            }
        }

        a[end+1]=tmp;
    }

}

void Print(int* a,int n)
{
    int i=0;
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}

int main()
{
    //插入排序
    int arr[]={1,9,0,2,3,4,6,5,8,9,6,7};
    InsertSort(arr,sizeof(arr)/sizeof(arr[0]));
    Print(arr,sizeof(arr)/sizeof(arr[0]));
    return 0;
}
